\section{Sampling Folklore Result}
\label{app:folklore-sampling}

\begin{theorem}
Let $Y_1, \ldots, Y_k$ be a random sample of $X_1, \ldots, X_n$, where $k < n$, $X_i \leq X_{i+1}$ for all $1 \leq i < n$, and $Y_i \leq Y_{i+1}$ for all $1 \leq i < k$. Then, if $k > \Theta(1/\epsilon^2)$, for any $0 \leq q \leq 1$, the value $Y_{\lfloor qk\rfloor}$ is one of $X_{\lfloor n(q - \epsilon)\rfloor}, \ldots, X_{\lfloor n(q + \epsilon)\rfloor}$ with constant probability. 
\end{theorem}

\begin{proof}
Let $k$, $n$, the $X_i$ and $Y_i$ be as in the statement of the theorem. The sampled value $Y_{\lfloor qk\rfloor}$ is one of $X_{\lfloor n(q - \epsilon)\rfloor}, \ldots, X_{\lfloor n(q + \epsilon)\rfloor}$ exactly when there are at least $\lfloor qk\rfloor$ sampled values larger than $X_{\lfloor n(q - \epsilon)\rfloor}$ and at least $\lfloor (1 - q)k\rfloor$ sampled values less than $X_{\lfloor n(q + \epsilon)\rfloor}$.

Define random variables Ai if ith smallest is at least X...
Chernoff bound for first part

Define random variables Ai if ith smallest is at most X...
Chernoff bound for second part  
\end{proof}
